package 第4节面向对象;

import java.util.Comparator;

//自定义的顺序表
//E 所存储元素的数据类型 未知
public class ArrayList<E>{
    //存储元素的容器
    private E[] data;
    //元素的有效个数
    private int size;
    //最小默认容量
    private int capacity;

    //构造函数
    public ArrayList() {
        capacity = 10;
        size = 0;
        data = (E[]) new Object[capacity];
    }

    //默认在表尾添加一个元素
    public void add(E element) {
        insert(size, element);
    }

    //在指定角标index处插入一个元素
    public void insert(int index, E element) {
        if (index < 0 || index > size) {
            throw  new IllegalArgumentException("insert 角标非法");
        }
        //特殊：表已经满了->扩容
        if (size == data.length) {
            System.out.println("扩容");
            resize(data.length * 2);
        }
        for (int i = size - 1; i >= index; i--) {
            data[i + 1] = data[i];
        }
        data[index] = element;
        size++;
    }

    //删除指定角标index处的元素,并返回其值
    public E delete(int index) {
        if (index < 0 || index >= size) {
            throw new IllegalArgumentException("delete 角标非法");
        }
        E ret = data[index];
        for (int i = index + 1; i < size; i++) {
            data[i - 1] = data[i];
        }
        size--;
        //特殊：缩容
        if (size == data.length / 4 && data.length > capacity) {
            System.out.println("缩容");
            resize(data.length / 2);
        }

        return ret;
    }

    //扩容操作
    private void resize(int newLength) {
        E[] newData = (E[]) new Object[newLength];
        for (int i = 0; i < size; i++) {
            newData[i] = data[i];
        }
        data = newData;
    }

    //从左到右删除第一次出现的数据e
    public void remove(E element) {
        int index = indexOf(element);
        if (index != -1) {
            delete(index);
        }
    }

    //获取指定角标index处的元素
    public E get(int index) {
        if (index < 0 || index >= size) {
            throw new IllegalArgumentException("get 角标非法");
        }
        return data[index];
    }

    //修改指定角标index处的元素为新元素，并返回其原先的元素
    public E set(int index, E newElement) {
        if (index < 0 || index >= size) {
            throw new IllegalArgumentException("get 角标非法");
        }
        E ret = data[index];
        data[index] = newElement;
        return ret;
    }

    //判断元素e是否存在于表中
    public boolean contains(E element) {
        return indexOf(element) != -1;
    }

    public int size() {
        return size;
    }

    public void clear() {
        capacity = 10;
        size = 0;
        data = (E[]) new Object[capacity];
    }



    //查找元素e从左到右第一次出现的角标
    public int indexOf(E element) {
        for (int i = 0; i < size; i++) {
            if (data[i].equals(element)) {
                return i;
            }
        }
        return -1;
    }

    //判断表是否为空
    public boolean isEmpty() {
        return size == 0;
    }

    public void sort(Comparator<E> comparator) {
        quickSort(0,size - 1, comparator);
    }

    private void quickSort(int l, int r, Comparator<E> comparator) {
        if (l >= r) {
            return;
        }
        E v = data[l];
        int lt = l;
        int gt = r + 1;
        int i = l + 1;
        while (i < gt) {
            if (comparator.compare(data[i], v) < 0) {
                swap(lt + 1, i);
                lt++;
                i++;
            } else if (comparator.compare(data[i], v) > 0) {
                swap(i,gt - 1);
                gt--;
            } else {
                i++;
            }
        }
        swap(lt,l);
        //处理左边
        quickSort(l, lt - 1,comparator);
        //处理右边
        quickSort(gt,r,comparator);
    }

    private void swap(int i, int j) {
        E temp = data[i];
        data[i] = data[j];
        data[j] = temp;
    }

    /*
    从Object类继承而来的函数
    将对象中的核心数据拼接成一个字符串并进行返回
    []
    [1, 2, 3, 4, 5]
    */
    @Override
    public String toString() {
        StringBuilder sb = new StringBuilder();
        sb.append('[');
        if (isEmpty()) {
           sb.append(']');
        } else {
            for (int i = 0; i < size; i++) {
                sb.append(data[i]);
                if (i == size - 1) {
                    sb.append(']');
                } else {
                    sb.append(',');
                    sb.append(' ');
                }
            }
        }
        return sb.toString();
    }
}
